/**
 * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
 */
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var ans, res, hash, len;

function dfs(num, nums) {
  if (num === len) {
    var tmp = res.map(function (item) {
      return item;
    });

    ans.push(tmp);
    return;
  }

  for (var i = 0; i < len; i++) {
    if (hash[i]) continue;
    hash[i] = true;
    res.push(nums[i]);
    dfs(num + 1, nums);
    hash[i] = false;
    res.pop();
  }
}

var permute = function (nums) {
  len = nums.length,
    ans = [],
    res = [],
    hash = [];

  dfs(0, nums);
  return ans;
};

console.log(permute([1, 2, 3])); // [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
console.log(permute([0, 1])); // [ [ 0, 1 ], [ 1, 0 ] ]
console.log(permute([1])); // [ [ 1 ] ]

var permute = function (nums) {
  const res = [], path = [];
  backtracking(nums, nums.length, []);
  return res;

  function backtracking(n, k, used) {
    if (path.length === k) {
      res.push(Array.from(path));
      return;
    }
    for (let i = 0; i < k; i++) {
      if (used[i]) continue;
      path.push(n[i]);
      used[i] = true; // 同支
      backtracking(n, k, used);
      path.pop();
      used[i] = false;
    }
  }
};

console.log(permute([1, 2, 3])); // [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
console.log(permute([0, 1])); // [ [ 0, 1 ], [ 1, 0 ] ]
console.log(permute([1])); // [ [ 1 ] ]
